基于边重要度的矩阵分解链路预测算法

doi:10.16451/j.cnki.issn1003-6059.201802006

Abstract
Figure/Table
References (44)
Related Citation (13)

Download: PDF (683 KB) HTML (1 KB)
Export: BibTeX | EndNote (RIS)

Abstract

The domain adaptability of link prediction method based on matrix factorization is fine. However, in the existing link prediction method based on matrix factorization, the network data representation of 0-1 matrix has a strong assumption of unknown edge in the network, while the importance of the known edges in the network is indistinguishable. The network data representation hypothesis of 0-1 matrix is relaxed in this paper, and no assumption to the edges of the unknown node-pairs is made. The measure method of importance of edges is put forward. Finally, the link prediction model based on the network weight matrix factorization is established by measuring the importance of the known edges in the network. The model is compared with the prediction algorithms based on metric and matrix factorization. Experimental results on eight public network datasets show the proposed algorithm is more effective.

Key words： Link Prediction Matrix Factorization Importance of Edges

Received: 12 May 2017

ZTFLH:

TP 391

Fund:

Supported by National Natural Science Foundation of China(No.U1435212,U61432011), The Key Scientific and Technological Project of Shanxi Province(No.MQ2014-09)

About author:: GUO Liyuan, master student. Her resear-ch interests include social computing.WANG Zhiqiang, Ph.D. candidate. His research interests include social network analy-sis and machine learning.LIANG Jiye, Ph.D., professor. His research interests include granular computing, data mining and machine learning.

	Service

	E-mail this article
	Add to my bookshelf
	Add to citation manager
	E-mail Alert
	RSS
	Articles by authors
	GUO Liyuan
	WANG Zhiqiang
	LIANG Jiye

Cite this article:

GUO Liyuan,WANG Zhiqiang,LIANG Jiye. Link Prediction Algorithm by Matrix Factorization Based on Importance of Edges[J]. , 2018, 31(2): 150-157.

URL:

http://manu46.magtech.com.cn/Jweb_prai/EN/10.16451/j.cnki.issn1003-6059.201802006 OR http://manu46.magtech.com.cn/Jweb_prai/EN/Y2018/V31/I2/150

[1] HASAN M A, ZAKI M J. A Survey of Link Prediction in Social Networks // AGGARWAL C C, eds. Social Network Data Analytics. New York, USA: Springer, 2011: 243-275.
[2] MA H, YANG H X, LYU M R, et al. SoRec: Social Recommendation Using Probabilistic Matrix Factorization // Proc of the 17th ACM Conference on Information and Knowledge Management. New York, USA: ACM, 2008: 931-940.
[3] WANG Z Q, LIANG J Y, LI Y, et al. An Approach to Cold-Start Link Prediction: Establishing Connections between Non-topological and Topological Information. IEEE Transactions on Knowledge and Data Engineering, 2016, 28(11): 2857-2870.
[4] LIBEN-NOWELL D, KLEINBERG J. The Link-Prediction Problem for Social Networks. Journal of the American Society for Information Science and Technology, 2007, 58(7): 1019-1031.
[5] MITZENMACHER M. A Brief History of Generative Models for Power Law and Lognormal Distributions. Internet Mathematics, 2004, 1(2): 226-251.
[6] ADAMIC L A, ADAR E. Friends and Neighbors on the Web. Social Networks, 2003, 25(3): 211-230.
[7] ZHOU T, LÜ L Y, ZHANG Y C. Predicting Missing Links via Local Information. The European Physical Journal B, 2009, 71(4): 623-630.
[8] KATZ L. A New Status Index Derived from Sociometric Analysis. Psychometrika, 1953, 18(1): 39-43.
[9] JEH G, WIDOM J. SimRank: A Measure of Structural-Context Similarity // Proc of the 8th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York, USA: ACM, 2002: 538-543.
[10] BRIN S, PAGE L. Reprint of: The Anatomy of a Large-Scale Hypertextual Web Search Engine. Computer Networks and ISDN Systems, 2012, 56(18): 3825-3833.
[11] CLAUSET A, MOORE C, NEWMAN M E J. Hierarchical Structure and the Prediction of Missing Links in Networks. Nature, 2008, 453: 98-101.
[12] WHITE H C, BOORMAN S A, BREIGER R L. Social Structure from Multiple Networks: I. Blockmodels of Roles and Positions. The American Journal of Sociology, 1976, 81(4): 730-780.
[13] ANDERSON C J, WASSERMAN S, FAUST K. Building Stochastic Boockmodels. Social Networks, 1992, 14(1/2): 137-161.
[14] DORELAN P, BATAGELJ V, FERLIGOJ A. Generalized Blockmodeling. Cambridge, UK: Cambridge University Press, 2004.
[15] 吴祖峰,梁棋,刘峤,等.基于AdaBoost的链路预测优化算法.通信学报, 2014, 35(3): 116-123.
(WU Z F, LIANG Q, LIU J, et al. Modified Link Prediction Algorithm Based on AdaBoost. Journal of Communication, 2014, 35(3): 116-123.)
[16] PAN Y, LAI H J, LIU C, et al. Rank Aggregation via Low-Rank and Structured-Sparse Decomposition // Proc of the 27th AAAI Conference on Artificial Intelligence. Palo Alto, USA: AAAI Press, 2013: 760-766.
[17] LEE J, KIM S, LEBANON G, et al. Local Low-Rank Matrix Approximation // Proc of the 30th International Conference on Machine Learning. Cambridge, USA: The MIT Press, 2013: 82-90.
[18] ZHENG Y G, ZHANG X R, YANG S Y, et al. Low-Rank Representation with Local Constraint for Graph Construction. Neurocomputing, 2013, 122: 398-405.
[19] BILLSUS D, PAZZANI M J. Learning Collaborative Information Filters // Proc of the 15th International Conference on Machine Learning. San Francisco, USA: Morgan Kaufmann, 1998: 46-54.
[20] YAZAMA Y, MITSUKURA Y, FUKUMI M, et al. Recognition from EMG Signals by an Evolutional Method and Non-negative Matrix Factorization // Proc of the 7th International Conference on Knowledge-Based Intelligent Information and Engineering Systems. New York, USA: Springer, 2003, I: 594-600.
[21] SALAKHUTDINOV R, MNIH A. Probalistic Matrix Factorization[C/OL]. [2017-04-28]. https://papers.nips.cc/paper/3208-probabilistic-matrix-factorization.pdf.
[22] SALAKHUTDINOV R. Bayesian Probabilistic Matrix Factorization Using MCMC[C/OL]. [2017-04-28]. http://www.cs.toronto.edu/~rsalakhu/papers/bpmf.pdf.
[23] LIU Y, WANG Z S, YIN J, et al. A Scalable Proximity Measure for Link Prediction via Low-Rank Matrix Estimation[C/OL]. [2017-04-28]. www.atlantis-press.com/php/download_paper.php?id=12639.
[24] MENON A K, ELKAN C. Link Prediction via Matrix Factorization // Proc of the Joint European Conference on Machine Learning and Knowledge Discovery in Databases. New York, USA: Springer, 2011, II: 437-452.
[25] PAGE L B, PERRY J E. Reliability Polynomials and Link Importance in Networks. IEEE Transactions on Reliability, 1994, 43(1): 51-58.
[26] NARDELLI E, PROIETTI G, WIDMAYER P. Finding the Detour-Critical Edge of a Shortest Path between Two Nodes. Information Processing Letters, 1998, 67(1): 51-54.
[27] NARDELLI E, PROIETTI G, WIDMAYER P. A Faster Computation of the Most Vital Edge of a Shortest Path. Information Processing Letters, 2001, 79(2): 81-85.
[28] TRALDI L. Commentary on: Reliability Polynomials and Link Importance in Networks. IEEE Transactions on Reliability, 2000, 49(3): 322.
[29] HSU L H, JAN R H, LEE Y C, et al. Finding the Most Vital Edge with Respect to Minimum Spanning Tree in Weighted Graphs. Information Processing Letters, 1991, 39(5): 277-281.
[30] RAO V V B. Most-Vital Edge of a Graph with Respect to Spanning Trees. IEEE Transactions on Reliability, 1998, 47(1): 6-7.
[31] TSEN F S P, SUNG T Y, LIN M Y, et al. Finding the Most Vital Edges with Respect to the Number of Spanning Trees. IEEE Transactions on Reliability, 1994, 43(4): 600-602.
[32] BALL M O, GOLDEN B L, VOHRA R V. Finding the Most Vital Arcs in a Network. Operations Research Letters, 1989, 8(2): 73-76.
[33] KOREN Y, BELL R, VOLINSKY C. Matrix Factorization Techniques for Recommender Systems. Computer, 2009, 42(8): 30-37.
[34] SALAKHUTDINOV R, MNIH A. Probabilistic Matrix Factorization[C/OL]. [2017-04-28]. https://papers.nips.cc/paper/3208-probabilistic-matrix-factorization.pdf.
[35] ZACHARY W W. An Information Flow Model for Conflict and Fission in Small Groups. Journal of Anthropological Research, 1977, 33(4): 452-473.
[36] LÓPEZ B D, SHIRAI J A B. Marine Aquaculture and Bottlenose
Dolphins′(Tursiops Truncatus) Social Structure. Behavioral Ecology & Sociobiology, 2008, 62: 887-894.
[37] KNUTH D E. The Stanford GraphBase: A Platform for Computing. New York, USA: ACM, 1993.
[38] WATTS D J, STROGATZ S H. Collective Dynamics of ′Small World′ Networks. Nature, 1998, 393: 440-442.
[39] KRSTULOVIC S, HUNECKE A, SCHRÖDER M. An HMM-Based Speech Synthesis System Applied to German and Its Adaptation to a Limited Set of Expressive Football Announcements // Proc of the 8th Annual Conference of the International Speech Communication Association. Berlin, Germany: Springer, 2007:1897-1900.
[40] ALMUNIA J, BASTERRETXEA G, ARISTEGUI J, et al. Benthic-Pelagic Switching in a Coastal Subtropical Lagoon. Estuarine, Coastal and Shelf Science, 1999, 49(3): 363-384.
[41] LÜ L Y, ZHOU T. Link Prediction in Complex Networks: A Survey. Physica A: Statistical Mechanics and Its Applications, 2011, 390(6): 1150-1170.
[42] 吕琳媛.复杂网络链路预测.电子科技大学学报, 2010, 39(5): 651-661.
(LÜ L Y. Link Prediction on Complex Networks. Journal of University of Electronic Science & Technology of China, 2010, 39(5): 651-661.)
[43] KALMAN D. A Singularly Valuable Decomposition: The SVD of a Matrix. The College Mathematics Journal, 1996, 27(1): 2-23
[44] SPRING N, MAHAJAN R, WETHERALL D, et al. Measuring ISP Topologies with Rocketfuel. IEEE/ACM Transactions on Networking, 2004, 12(1): 2-16.